/**
 * 不同的子序列
 *
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
 * 测试用例保证结果在 32 位有符号整数范围内。
 *
 * 示例 1：
 * 输入：s = "rabbbit", t = "rabbit"
 * 输出：3
 * 解释：
 * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
 * rabbbit
 * rabbbit
 * rabbbit
 *
 * 示例 2：
 * 输入：s = "babgbag", t = "bag"
 * 输出：5
 * 解释：
 * 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 *
 * 提示：
 * 1 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 */

/**
 * 看到两个字符串,  子序列, 我们优先考虑动态规划
 * dp[i][j] : s -> 0 ~ i 组合覆盖 t -> 0 ~ j 有多少个组合
 * 动态规划就是使用前面的状态来表示当前的状态
 * 首先, 无论现在这个节点的字符是啥, 一定会有不要这个地方的组合个数
 * dp[i][j] = dp[i - 1][j]
 * 其次, 我们这里的 s 要是和 t 字符相等, 那么就又要加上一种情了
 * s[i] == t[j] : dp[i][j] += dp[i - 1][j - 1];
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {
    public int numDistinct(String s, String t) {

        int m = s.length(), n = t.length();

        if (m < n) {
            return 0;
        }

        int[][] dp = new int[m + 1][n + 1];

        // 初始化, 我们的 t 为 0 的组合数都有一种
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        // 其实这里要是 i < j 肯定是没有可能的, 但是在条件上是加不上的
        // 不然会越界, 但是我们可以在循环内加上条件
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // 第一种情况
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }

                // 第二种情况
                dp[i][j] += dp[i - 1][j];
            }
        }

        //返回
        return dp[m][n];
    }
}